class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;

        vector<int> dp = nums;
        int res = dp[0];
        for(int i = 1; i < nums.size(); i++)
        {
            dp[i] = std::max(dp[i]+dp[i-1], dp[i]);
            res = std::max(res, dp[i]);
        }

        return res;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;

        int pre = nums[0];
        int res = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            int cnt = std::max(pre+nums[i], nums[i]);
            res = std::max(res, cnt);
            pre = cnt;
        }

        return res;
    }
};